package com.aqie.easy.binarySearchTree;

import com.aqie.easy.structure.TreeNode;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 538 把二叉搜索树转换为累加树
 * todo important
 */
public class ConvertBST {
    /**
     * 错误解 只有一层是正确的
     * @param root
     * @return
     */
    public TreeNode convertBST3(TreeNode root) {
        if (root == null) return null;

        root.val += getRootSum(root.right);
        if(root.left != null) root.left.val += root.val;
        if(root.right != null) root.right.val += getRightSum(root.right);
        return root;
    }

    private int getRootSum(TreeNode node){
        if (node != null){
            return getRightSum(node.left) + getRightSum(node.right) + node.val;
        }
        return 0;
    }

    private int getRightSum(TreeNode node){
        if (node != null){
            return getRightSum(node.left) + getRightSum(node.right);
        }
        return 0;
    }

    /**
     * 优先队列 + 先序遍历
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        int max = 0;
        TreeNode p = root;
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> priorityQueue = new PriorityQueue<>(5, Comparator.comparingInt(o -> o.val));
        queue.add(p);
        // 将树的所有节点进队
        while (!queue.isEmpty()){
            p = queue.poll();
            priorityQueue.add(p);
            max += p.val;
            if (p.left != null) queue.add(p.left);
            if (p.right != null) queue.add(p.right);
        }

        // 出队列
        while (!priorityQueue.isEmpty()){
            p = priorityQueue.poll();
            max -= p.val;
            p.val += max;
        }
        return root;

    }

    /**
     * 右中左的中序遍历，需要记录一个上一次遍历的累加和
     * @param root
     */
    public TreeNode convertBST2(TreeNode root) {

        search(root, 0);
        return root;
    }
    private int search(TreeNode root, int n) {
        if(root == null)
            return n;
        int right_val = search(root.right, n);
        root.val += right_val; //右中左的中序遍历，所以相加的操作只用在中间做就行了，其他的就是把参数传递到下一层
        return search(root.left, root.val);//这里是把左中右三个节点里最后一个遍历的左子节点的返回值，返回给下一层
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.right = new TreeNode(13);
        root.left = new TreeNode(2);

        new ConvertBST().convertBST(root);
    }
}
